package com.lx.algorithm.code;

import java.util.ArrayList;
import java.util.List;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-01 19:42:15
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-01     张李鑫                     1.0         1.0 Version
 */
public class Code13 {
    /**
     * 给定一个有序数组arr，给定一个正数aim
     * <p>
     * 1）返回累加和为aim的，所有不同二元组
     * <p>
     * 2）返回累加和为aim的，所有不同三元组
     */


    public static List<List<Integer>> printUniquePair(int[] arr, int target) {
        List<List<Integer>> list = new ArrayList<>();
        find(0, arr.length - 1, arr, target, list);
        return list;
    }

    //这里懒得实现了 如果是三个数字的话就从头开始遍历一遍 然后从index右边去找两个数等于 target-arr[index]的值
    public static List<List<Integer>> printUniquePairII(int[] arr, int target) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            find(0, arr.length - 1, arr, target, list);
        }

        return list;
    }

    public static void find(int l, int r, int[] arr, int target, List<List<Integer>> lists) {
        while (l <= r) {
            if (arr[l] + arr[r] == target && (arr[l] != arr[l + 1] || arr[r] != arr[r - 1])) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(arr[l]);
                list.add(arr[r]);
                lists.add(list);
                l++;
                r--;
            } else if (arr[l] + arr[r] > target) {
                r--;
            } else {
                l++;
            }
        }
    }

    public static void main(String[] args) {
        int sum = 10;
        int[] arr1 = {-8, -4, -3, 0, 1, 2, 4, 5, 8, 9};

        System.out.println("====");
        printUniquePair(arr1, sum);
        System.out.println("====");
        System.out.println(printUniquePair(arr1, sum));
    }
}